package eda.skipList;

import eda.util.ADTOverflowException;
import eda.util.ADTUnderflowException;


class SkipNode<V> {

	//the key of root is Integer.MIN_VALUE and NIL has key Integer.MAX_VALUE
	protected int key;
	protected int height;
	protected V satteliteData;
	protected SkipNode<V>[] forward;
	
	public SkipNode(int key, int height, V satelliteData){
		this.key = key;
		this.height = height;
		this.satteliteData = satelliteData;
		this.forward = new SkipNode[height];
	}
	
	/**
	 * Returns a String containing the print of a Skip list. The print of a node 
	 * has the format: <KEY,HEIGHT>(K0,K1,...,Kn), where
	 * - KEY is the key 
	 * - HEIGHT is the height;level
	 * - Ki is the key of the forward[i] pointer.
	 * - the KEY of the root node is printed as ROOT
	 * - the KEY of NIL is printed as NIL
	 */
	@Override
	public String toString(){

		String chave;
		
		if(this.key == Integer.MIN_VALUE){
			chave = "ROOT";
		}
		else{
			chave = ""+this.key;
		}
		
		StringBuilder sb = new StringBuilder();
		sb.append("<" + chave + "," + this.height + ">(");
		for(int i = 0; i < this.height; i ++){
			if(this.forward[i] != null){
				if(i < SkipListImpl.level){
					if(this.forward[i].key == Integer.MAX_VALUE){
						chave = "NIL";
					}
					else{
						chave = ""+this.forward[i].key;
					}
					sb.append(chave+",");
				}
			}
		}
		sb.deleteCharAt(sb.length()-1);
		sb.append(")");
		return sb.toString();
	}
}

/**
 * The interface of a skip list with a fized probability of 50%. It can use the 
 * max level as level or not. This is chosen by the user during the creation.
 *
 */
public interface SkipList<V> {
	/**
	 * Inserts a new node in a skip list with a random height.
	 */
	void insert(int key, V newValue) throws ADTOverflowException;

	/**
	 * Inserts a new node in a skip list with a given height.
	 */
	void insert(int key, V newValue, int height) throws ADTOverflowException;
	
	/**
	 * Removes a node of the skip list containing the given key.
	 * 
	 */
	void remove(int key) throws ADTUnderflowException;

	/**
	 * Returns the level/height of the highest node.
	 */
	int getHeight();

	/**
	 * Searches a node with a given key in the skip list.
	 * 
	 */
	SkipNode<V> search(int key);

	/**
	 * Returns the print of all nodes of the skip list in order. 
	 */
	String printSkipList();
}
